package com.wang.sort;

public class Demo19_Heap01 {
    //定义一个大根堆
    public static class MaxHeap {
        private int[] heap;
        private final int limit;
        private int heapSize;
        //初始化
        public MaxHeap(int limit) {
            this.limit = limit;
            heap = new int[limit];
            heapSize = 0;
        }

        public void push(int value) {
            if(heapSize == limit ) {
                throw new RuntimeException("heap is full!");
            }
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);

        }
        //返回大根堆的最大值，并在堆中删除该值。剩下的数依旧保持大根堆
        public int pop() {
            int res = heap[0];
            swap(heap, 0, --heapSize);
            heapify(heap, 0, heapSize);
            return res;
        }
        //从index位置下沉 比较该位置与其孩子节点位置元素的大小
        //若arr[index] < 孩子节点元素值 则交换
        //循环停止条件： index的孩子节点不再不比index位置值大 或者 没有孩子节点可比较
        private void heapify(int[] arr, int index, int heapSize) {
            int left = index * 2 + 1;
            while (left < heapSize) {
                // 比较左右孩子的大小，较大的孩子把下标给largest
                //有右孩子 && 右孩子值大于左孩子  否则 左
                int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
                int alllargest = arr[largest] > arr[index] ? largest : index;
                if(largest == index){
                    break;
                }
                swap(arr, largest, index);
                index = largest;
                left = index * 2 + 1;
            }
        }

        private void heapInsert(int[] arr, int index) {
            //待插入位置的元素跟他的父节点比较
            //当arr[index] == arr[(index - 1) / 2
            //1.index已到根节点 2.index位置元素等于其父节点元素值 跳出循环
            //所以arr[index] > arr[(index - 1) / 2 为循环条件
            while (arr[index] > arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] =temp;
        }

    }
}
